#include <stdio.h>
#include <stdlib.h>

// 定义AVL树结点结构
struct Node
{
    int data;           // 结点数据
    struct Node *left;  // 左子树指针
    struct Node *right; // 右子树指针
    int height;         // 结点高度（用于平衡因子计算）
};

// 计算结点高度（空结点高度为0）
int height(struct Node *node)
{
    if (node == NULL)
        return 0;
    return node->height;
}

// 获取两个整数中的较大值
int max(int a, int b)
{
    return (a > b) ? a : b;
}

// 创建新结点
struct Node *newNode(int data)
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // 新结点初始高度为1
    return node;
}

// 右旋转（处理LL不平衡）
struct Node *rightRotate(struct Node *y)
{
    struct Node *x = y->left;
    struct Node *T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x; // 返回新的根结点
}

// 左旋转（处理RR不平衡）
struct Node *leftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y; // 返回新的根结点
}

// 获取结点的平衡因子
int getBalance(struct Node *node)
{
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

// 向AVL树插入结点
struct Node *insert(struct Node *node, int data)
{
    // 1. 标准BST插入
    if (node == NULL)
        return newNode(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // 重复值不允许插入
        return node;

    // 2. 更新当前结点高度
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. 获取平衡因子检查是否不平衡
    int balance = getBalance(node);

    // 4. 处理四种不平衡情况

    // 左左情况（LL）
    if (balance > 1 && data < node->left->data)
        return rightRotate(node);

    // 右右情况（RR）
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);

    // 左右情况（LR）
    if (balance > 1 && data > node->left->data)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况（RL）
    if (balance < -1 && data < node->right->data)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 如果已平衡则返回原结点
    return node;
}

// 中序遍历（升序输出）
void inOrder(struct Node *root)
{
    if (root != NULL)
    {
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
}

// 主函数测试
int main()
{
    struct Node *root = NULL;

    // 测试插入序列
    int arr[] = {10, 20, 30, 40, 50, 25};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Inserting values: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
        root = insert(root, arr[i]);
    }
    printf("\n");

    // 打印中序遍历结果
    printf("Inorder traversal of the constructed AVL tree: ");
    inOrder(root);
    printf("\n");

    return 0;
}